package com.leetcode.程序员面试金典.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2021-04-21 12:17
 */
public class 面试题_17_22_单词转换 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    String beginWord = "hit";
    String endWord = "cog";
    List<String> wordList = new ArrayList<>(Arrays.asList("hot","dot","dog","lot","log","cog"));
    List<String> list = solution.findLadders(beginWord, endWord, wordList);
    System.out.println(list);
  }


  static
  class Solution {
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
      int endIndex = wordList.indexOf(endWord);
      if (endIndex == -1) {
        return new ArrayList<>();
      }
      int beginIndex = wordList.size();
      wordList.add(beginWord);

      // 将 wordList 构建成一个图
      int[][] graph = new int[wordList.size()][wordList.size()];
      for (int i = 0; i < graph.length; ++i) {
        graph[i][i] = 1;
        for (int j = i + 1; j < graph.length; ++j) {
          if (hasEdge(wordList.get(i), wordList.get(j))) {
            graph[i][j] = 1;
            graph[j][i] = 1;
          }
        }
      }
      // 使用 dijkstra 算法选择 beginWord 到 endWord 的最短路径
      Integer[] distance = new Integer[wordList.size()];
      Integer[] path = new Integer[wordList.size()];
      boolean[] flag = new boolean[wordList.size()];

      distance[beginIndex] = 0;
      path[beginIndex] = beginIndex;

      for (int i = 0; i < wordList.size(); ++i) {
        // 找到当前的最短路径的点
        int minDistance = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int j = 0; j < distance.length; ++j) {
          if (!flag[j] && distance[j] != null && distance[j] < minDistance) {
            minDistance = distance[j];
            minIndex = j;
          }
        }
        // 如果图中形成了岛屿，退出
        if (minIndex == -1) {
          break;
        }
        // 如果已找到目标点，退出
        if (minIndex == endIndex) {
          break;
        }
        // 标记已找到最短路径的点
        flag[minIndex] = true;
        // 通过当前点是否可以缩短其它点的路径
        for (int j = 0; j < distance.length; ++j) {
          if (graph[minIndex][j] == 1) {
            if (distance[j] == null || distance[j] > graph[minIndex][j] + minDistance) {
              distance[j] = graph[minIndex][j] + minDistance;
              path[j] = minIndex;
            }
          }
        }
      }

      LinkedList<String> result = new LinkedList<>();
      if (path[endIndex] == null) {
        return result;
      }
      while (endIndex != path[endIndex]) {
        result.addFirst(wordList.get(endIndex));
        endIndex = path[endIndex];
      }
      result.addFirst(beginWord);
      return result;
    }

    private boolean hasEdge(String p1, String p2) {
      int diff = 0;
      for (int i = 0; i < p1.length(); ++i) {
        if (p1.charAt(i) != p2.charAt(i)) {
          ++diff;
        }
        if (diff > 1) {
          return false;
        }
      }
      return true;
    }
  }

}
